package com.linearList;

/**
 * @Author: linKe
 * @Date: 2021/12/30 14:59
 * @FileName: DoubleLinkedList
 * @version: 1.0
 * @Description:  循环双链表实现类
 */
public class DoubleLinkedListCycle<T> {

    /**
     * 数据域结点 对象
     */
    DoubleNode<T> prev, next;

    /**
     * 空参构造
     */
    public DoubleLinkedListCycle() {
        this.prev = new DoubleNode<>();
        //尾结点没有应用上
        this.next = new DoubleNode<>();
        //this.init();
        //循坏指向  头结点的后继指向前驱
        this.prev.next = this.prev.prev;
        //头结点的 前驱指向后继
        this.prev.prev = this.prev.next;
    }

    /**
     * 初始化结点前驱后继赋值
     * 循环双链表
     */
    void init() {
        this.prev.next = this.next;
        //this.prev.prev = this.next;
        this.next.prev = this.prev;
        //this.next.next = this.prev;
    }

    /**
     * 先测试尾插法
     * @param values 数据源数组
     */
    public DoubleLinkedListCycle(T[] values) {
        //容器初始化
        this();
        //初始化一个双向结点对象p
        DoubleNode<T> p = this.prev;
        //p.next = this.next.prev;
        //p.prev = this.prev.next;
        for (int i = 0; i < values.length; i++) {
            //当数据域对象的值不为null时 进行结点赋值
            if (values[i] != null) {
                //当第一个头结点的prev 为空时 更改头结点的
                if (p.prev==null){
                    //给p结点初始赋值
                    p = new DoubleNode<T>(values[i], null, null);
                    //头结点的后继指向 为p
                    this.prev.next=p;
                    //p的前驱指向为头结点 默认头结点为固定结点
                    p.prev = this.prev;
                    //
                    //增加后继 和 前驱 的 循环
                    p.next = this.prev;
                    this.prev.prev = p.next;
                }else {
                    //初始化双链表结点值
                    p.next = new DoubleNode<T>(values[i], null, this.prev);
                    //p的前驱指向变换
                    p.prev = p;
                    //p的后继的前驱指向p的后继 进行中间插入值的变换
                    p.next.prev = p.next;
                    //this.next.prev = p.next;
                    p = p.next;
                    //
                    //增加后继 和 前驱 的 循环
                    //p.next = this.prev;
                    this.prev.prev = p.next;
                }
                //this.prev.next = p.next;

                //将当前后继结点的前驱 赋值给p结点的前驱
                //p.next.prev = this.prev;


                //p=p.next;
                //将当前前驱结点的后继 赋值为 p

                //p的后继 赋值为当前后继结点
                //p.next = p;
                //当前后继结点的前驱 赋值为p
                //this.next.prev = p;
            }
        }
    }

    /**
     * 根据序号查询第i个元素
     *
     * @param i 序号值
     * @return 结果
     */
    T get(int i) {
        //初始化双链结点对象
        DoubleNode<T> p =this.prev;
        //遍历查找第i个对象，当p的后继为null时终止循环
        for (int j = 0; p.next != null && j < i; j++) {
            //将p的后继赋值给p
            p = p.next;
        }
        //返回p的数据域结果
        return p.data;
    }

    /**
     * 删除序号第i个的双结点对象，返回对象i的数据域的值
     *
     * @param i 序号i的值
     * @return 结果
     */
    T remove(int i) {
        //初始化结点对象
        //DoubleNode<T> p = new DoubleNode<>();
        //初始赋值为头结点 开始判断
        DoubleNode<T> p = this.prev;

        //遍历查找第i个对象，当p的后继为null时终止循环
        for (int j = 0; p.next != null && j < i; j++) {
            p = p.next;
        }
        if (i >= 0 && p.next != null) {
            //获取旧的数据域的值
            T old = p.data;
            //修改    p的后继 为 后继的后继
            p.next = p.next.next;
            //修改    p的前驱 为 前驱的前驱
            p.prev = p.prev.prev;
            /*
            原写法 并没有移除要删掉的结点
            将p的前驱域的后继结点 赋值为p的后继
            p.prev.next = p.next;
            //将p的后继域的前驱结点 赋值为p的前驱   将p结点就悬置了
            p.next.prev = p.prev;
            //返回删除的数据域的值

             */
            return old;
        }
        //不存在则返回null
        return null;
    }

    /**
     * 根据序号设定，第i个元素结点的值
     *
     * @param i 序号
     * @param x 要设置的数据值
     */
    void set(int i, T x) {
        if (x == null) {
            //数据值非空判断
            throw new NullPointerException("x==null");
        }
        //初始化结点 为头结点
        DoubleNode<T> p = this.prev;
        //遍历 查找序号第i-1个的结点   当头结点的的后继指向不为null 进行判断
        for (int j = 0; p.next != null && j < i; j++) {
            p = p.next;
        }
        //p.next  遍历得到当前插入的序号的结点对象 赋值
        if (i >= 0 && p.next != null) {
            p.data = x;
        } else {
            //序号对应的结果不存在 返回对象索引越界异常
            throw new IndexOutOfBoundsException(i + "");
        }

    }

    /**
     * 根据数据域的值查找第一个匹配的双结点
     *
     * @param key 数据值
     * @return 结果
     */
    DoubleNode<T> search(T key) {
        //初始化结点p为当前后继结点的前驱  p.next作为判断条件 而不是p
        //this.prev.next 初始赋值更改为第一个结点开始遍历 也就是空头结点的后继结点  这时 p可以作为判断对象
        for (DoubleNode<T> p = this.prev.next; p != null; p = p.next) {
            if (p.data.equals(key)) {
                //将数据域的值进行比较
                return p;
            }
        }
        //没有匹配结果返回null
        return null;
    }

    /**
     * 插入结点
     * 查找到底i个元素的位置，并将数据域的值修改为x
     * @param i 遍历序号
     * @param x 数据域的值
     * @return  结果
     */
    DoubleNode<T> insert(int i ,T x){
        if (x==null){
            //数据值非空判断
            throw new NullPointerException("x==null");
        }
        //初始化赋值
        //DoubleNode<T> p = new DoubleNode<>();
        //修改赋值为当前结构的
        DoubleNode<T> p = this.prev;
        //遍历双链表 查找第i-1个元素的结点
        for (int j = 0;p.next!=null&& j < i; j++) {
            p = p.next;
        }
        //在第i个元素后追加结点
        p.next = new DoubleNode<>(x, p.prev, p.next);
        //返回插入的结点
        return p.next;
    }

    /**
     * 统计双向链表的结点数
     * @return  结果
     */
    int size(){
        //声明变量用于计数
        int count = 0;
        //遍历双向链表的已有数据 从第一个结点开始 头结点的后继指向
        for (DoubleNode<T> p = this.prev.next;p!=null;p=p.next){
            count++;
        }
        //返回统计结果
        return count;
    }

    /**
     * 重写比较方法
     * @param obj   比较对象
     * @return  结果
     */
    @Override
    public boolean equals(Object obj){
        if (obj==this){
            return true;
        }
        if (!(obj instanceof DoubleLinkedListCycle<?>)){
            return false;
        }
        //获取进行对象比较的结点   p
        DoubleNode<T> p = this.prev.next;
        //传入对象进行比较的结点   q
        DoubleNode<?> q = ((DoubleLinkedListCycle<?>) obj).prev.next;
        //遍历循环比较
        while (p!=null&&q!=null&&q.data.equals(p.data)){
            p = p.next;
            q = q.next;
        }
        //返回pq都为空对象的结果（表明两个链表相等），及最终都遍历完毕
        //return p!=null && q!=null;
        //
        return p==null && q==null;
    }
}
